<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <base data-ice="baseUrl" href="../../../">
  <title data-ice="title">src/collision/ObjectsKdTree3.js | xeokit-bim-viewer</title>
  <link type="text/css" rel="stylesheet" href="css/style.css">
  <link type="text/css" rel="stylesheet" href="css/prettify-tomorrow.css">
  <script src="script/prettify/prettify.js"></script>
  <script src="script/manual.js"></script>
<meta name="description" content="BIM viewer built on xeokit"><meta property="og:type" content="website"><meta property="og:url" content="https://github.com/xeokit/xeokit-bim-viewer"><meta property="og:site_name" content="xeokit-bim-viewer"><meta property="og:title" content="xeokit-bim-viewer"><meta property="og:image" content="./images/logo.jpg"><meta property="og:description" content="BIM viewer built on xeokit"><meta property="og:author" content="http://xeolabs.com"><meta property="twitter:card" content="summary"><meta property="twitter:title" content="xeokit-bim-viewer"><meta property="twitter:description" content="BIM viewer built on xeokit"><meta property="twitter:image" content="./images/logo.jpg"></head>
<body class="layout-container" data-ice="rootContainer">

<header>
  <a href="./" style="display: flex; align-items: center;"><img src="./image/brand_logo.jpg" style="width:34px;"></a>
  
  <a href="identifiers.html">Reference</a>
  <a href="source.html">Source</a>
  
  <div class="search-box">
  <span>
    <img src="./image/search.png">
    <span class="search-input-edge"></span><input class="search-input"><span class="search-input-edge"></span>
  </span>
    <ul class="search-result"></ul>
  </div>
<a style="position:relative; top:3px;" href="https://github.com/xeokit/xeokit-bim-viewer"><img width="20px" src="./image/github.png"></a></header>

<nav class="navigation" data-ice="nav"><div>
  <ul>
    
  <li data-ice="doc"><span data-ice="kind" class="kind-class">C</span><span data-ice="name"><span><a href="class/src/BIMViewer.js~BIMViewer.html">BIMViewer</a></span></span></li>
<li data-ice="doc"><a data-ice="dirPath" class="nav-dir-path" href="identifiers.html#collision">collision</a><span data-ice="kind" class="kind-class">C</span><span data-ice="name"><span><a href="class/src/collision/ObjectsKdTree3.js~ObjectsKdTree3.html">ObjectsKdTree3</a></span></span></li>
<li data-ice="doc"><a data-ice="dirPath" class="nav-dir-path" href="identifiers.html#server">server</a><span data-ice="kind" class="kind-class">C</span><span data-ice="name"><span><a href="class/src/server/Server.js~Server.html">Server</a></span></span></li>
</ul>
</div>
</nav>

<div class="content" data-ice="content"><h1 data-ice="title">src/collision/ObjectsKdTree3.js</h1>
<pre class="source-code line-number raw-source-code"><code class="prettyprint linenums" data-ice="content">import {math} from &quot;@xeokit/xeokit-sdk/dist/xeokit-sdk.es.js&quot;;

const MAX_KD_TREE_DEPTH = 15; // Increase if greater precision needed
const kdTreeDimLength = new Float32Array(3);

/**
 * A k-d tree for World-space 3D Entity collision detection with AABBs and frustums.
 */
export class ObjectsKdTree3 {

    constructor(cfg) {

        if (!cfg) {
            throw &quot;Parameter expected: cfg&quot;;
        }

        if (!cfg.viewer) {
            throw &quot;Parameter expected: cfg.viewer&quot;;
        }

        this.viewer = cfg.viewer;

        this._maxTreeDepth = cfg.maxTreeDepth || MAX_KD_TREE_DEPTH;
        this._root = null;
        this._needsRebuild = true;

        this._onModelLoaded = this.viewer.scene.on(&quot;modelLoaded&quot;, (modelId) =&gt; {
            this._needsRebuild = true;
        });

        this._onModelUnloaded = this.viewer.scene.on(&quot;modelUnloaded&quot;, (modelId) =&gt; {
            this._needsRebuild = true;
        });
    }

    /**
     * Gets the root ObjectsKdTree3 node.
     */
    get root() {
        if (this._needsRebuild) {
            this._rebuild();
        }
        return this._root;
    }

    _rebuild() {
        const viewer = this.viewer;
        const scene = viewer.scene;
        const depth = 0;
        this._root = {
            aabb: scene.getAABB()
        };
        for (let objectId in scene.objects) {
            const entity = scene.objects[objectId];
            this._insertEntity(this._root, entity, depth + 1);
        }
        this._needsRebuild = false;
    }

    _insertEntity(node, entity, depth) {

        const entityAABB = entity.aabb;

        if (depth &gt;= this._maxTreeDepth) {
            node.entities = node.entities || [];
            node.entities.push(entity);
            return;
        }
        if (node.left) {
            if (math.containsAABB3(node.left.aabb, entityAABB)) {
                this._insertEntity(node.left, entity, depth + 1);
                return;
            }
        }
        if (node.right) {
            if (math.containsAABB3(node.right.aabb, entityAABB)) {
                this._insertEntity(node.right, entity, depth + 1);
                return;
            }
        }
        const nodeAABB = node.aabb;
        kdTreeDimLength[0] = nodeAABB[3] - nodeAABB[0];
        kdTreeDimLength[1] = nodeAABB[4] - nodeAABB[1];
        kdTreeDimLength[2] = nodeAABB[5] - nodeAABB[2];
        let dim = 0;
        if (kdTreeDimLength[1] &gt; kdTreeDimLength[dim]) {
            dim = 1;
        }
        if (kdTreeDimLength[2] &gt; kdTreeDimLength[dim]) {
            dim = 2;
        }
        if (!node.left) {
            const aabbLeft = nodeAABB.slice();
            aabbLeft[dim + 3] = ((nodeAABB[dim] + nodeAABB[dim + 3]) / 2.0);
            node.left = {
                aabb: aabbLeft
            };
            if (math.containsAABB3(aabbLeft, entityAABB)) {
                this._insertEntity(node.left, entity, depth + 1);
                return;
            }
        }
        if (!node.right) {
            const aabbRight = nodeAABB.slice();
            aabbRight[dim] = ((nodeAABB[dim] + nodeAABB[dim + 3]) / 2.0);
            node.right = {
                aabb: aabbRight
            };
            if (math.containsAABB3(aabbRight, entityAABB)) {
                this._insertEntity(node.right, entity, depth + 1);
                return;
            }
        }
        node.entities = node.entities || [];
        node.entities.push(entity);
    }

    /**
     * Destroys this ObjectsKdTree3.
     */
    destroy() {
        const scene = this.viewer.scene;
        scene.off(this._onModelLoaded);
        scene.off(this._onModelUnloaded);
        this._root = null;
        this._needsRebuild = true;
    }
}
</code></pre>

</div>

<footer class="footer">
  Generated by <a href="https://esdoc.org">ESDoc<span data-ice="esdocVersion">(1.1.0)</span><img src="./image/esdoc-logo-mini-black.png"></a>
</footer>

<script src="script/search_index.js"></script>
<script src="script/search.js"></script>
<script src="script/pretty-print.js"></script>
<script src="script/inherited-summary.js"></script>
<script src="script/test-summary.js"></script>
<script src="script/inner-link.js"></script>
<script src="script/patch-for-local.js"></script>
</body>
</html>
